import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

class Solution {
    private HashMap<Integer, Integer> hash = new HashMap<>();

    public int integerReplacement(int n) {
        // Check if the result is already computed
        if (hash.containsKey(n)) {
            return hash.get(n);
        }



        // Base case
        if (n == 1) {
            return 0;
        }

        int result;
        if (n % 2 == 0) {
            result = integerReplacement(n / 2) + 1;
        } else {

            result = Math.min(integerReplacement(n /2), integerReplacement(n/2+1)) + 2;
        }

        hash.put(n, result);

        return result;
    }
}



class Solution1 {
    public int integerReplacement(int n) {
        int ret=0;

        while(n!=1){

            if(n==3) return ret+2;

            if(n%2==0){
                n/=2;
                ret++;
            }
            else{
                if(n%4==1){
                    n=(n-1)/2;
                }else{
                    n=n/2+1;
                }
                ret+=2;

            }
        }

        return ret;

    }
}





class Solution3 {
    public int maxEnvelopes(int[][] envelopes) {
        int n=envelopes.length;
        ArrayList<Integer> arr=new ArrayList<>();
        Arrays.sort(envelopes,(a,b)->{
            if(a[0]!=b[0]) return a[0]-b[0];
            else return b[1]-a[1];
        });

        arr.add(envelopes[0][1]);

        for(int i=1;i<n;i++){
            int num=envelopes[i][1];
            if(num>arr.get(arr.size()-1)) arr.add(num);
            else{
                int left=0;
                int right=arr.size()-1;
                int mid=(right-left)/2+left;
                while(left<right){
                    mid=(right-left)/2+left;
                    if(arr.get(mid)<num) left=mid+1;
                    else right=mid;
                }
                arr.set(right,num);
            }

        }

        return arr.size();

    }
}

